#include<iostream>
#include<cstring>
#include<queue>
#include<sys/time.h>
using namespace std;
const int N = 10000, M = N*N;
int h[N], e[M], ne[M], w[M], idx;
int q[N], head, tail=-1;
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
typedef pair<int, int> PII;
int st[N], dist[N];
void SPFA(int n) {
	q[++tail] = 5;
	dist[1] = 0;
	st[1] = 1;
	while (head<=tail) {
		int t = q[head++];
		for (int i = h[t]; ~i; i = ne[i]) {
			int j = e[i];
			if (dist[j] > dist[t] + w[i]) {
				dist[j] = dist[t] + w[i];
				if (!st[j]) {
					q[++tail] = j;
					st[j] = 1;
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i)
		if (dist[i] >= 0x3f3f3f3f / 2)
			dist[i] = -1;
}
int main(int argc,char** args) {
	memset(dist, 0x3f, sizeof dist);
	memset(h, -1, sizeof h);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		scanf("%d%d%d",&a,&b,&c);
		add(a, b, c);
	}

	
    struct timeval t1,t2;
    double time=0.0;
	gettimeofday(&t1,NULL);
	////
	SPFA(n);
	////
	gettimeofday(&t2,NULL);
	time=(double)(t2.tv_sec-t1.tv_sec)*1000.0 + (double)(t2.tv_usec-t1.tv_usec)/1000.0;
	cout<< time;
}